package co.recloud.ariadne.list;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * Created by IntelliJ IDEA.
 * User: alex
 * Date: 3/18/12
 * Time: 3:44 PM
 * To change this template use File | Settings | File Templates.
 */
public class SelfOrganizingList<T> implements Iterable<T> {
    private class Entry {
        T key;
        Entry next;
        Entry prev;
    }

    private Entry head;
    private Entry tail;
    private Map<T, Entry> entries;
    private int counter;
    private int modulus;
    private int capacity;
    private int size;
    
    public SelfOrganizingList(int capacity) {
        counter = 0;
        modulus = 0;
        entries = new HashMap<T, Entry>(size);
        this.capacity = capacity;
        size = 0;
    }

    private SelfOrganizingList moveToFront(T key) {
        Entry current = entries.get(key);
        if(current != null && current != head) {
            if(current == tail) {
                tail = current.prev;
            }
            if(current.prev != null) {
                current.prev.next = current.next;
            }
            if(current.next != null) {
                current.next.prev = current.prev;
            }
        } else if (current == null) {
            current = new Entry();
            current.key = key;
            entries.put(key, current);
        }
        if (head != null) {
            head.prev = current;
        }
        current.next = head;
        head = current;
        if(head.next == null) {
            tail = current;
        }
        return this;
    }

    private SelfOrganizingList transpose(T key) {
        Entry current = entries.get(key);
        Entry pp = null, p = null, n = null;
        if(current != null) {
            n = current.next;
            p = current.prev;
            if(current.prev != null) {
                if(current.prev.prev != null) {
                    pp = current.prev.prev;
                    pp.next = current;
                    current.prev = pp;
                }
                p.next = n;
                p.prev = current;
                current.next = p;
            }
            if (n != null) {
                n.prev = p;
            }
        } else {
            current = new Entry();
            current.key = key;
            entries.put(key, current);
            if (tail != null) {
                if (tail.prev != null) {
                    p = tail.prev;
                    p.next = current;
                }
                current.prev = p;
                current.next = tail;
                tail.prev = current;
            } else {
                head = current;
                tail = current;
            }
        }
        if (current.prev == null) {
            head = current;
        }
        if (current.next == null) {
            tail = current;
        }
        return this;
    }

    private SelfOrganizingList evict() {
        if(tail != null) {
            entries.remove(tail.key);
            tail = tail.prev;
            tail.next = null;
        }
        return this;
    }
    public synchronized SelfOrganizingList lookup(T key) {
        counter++;
        modulus = (((modulus << 1) + 1) % capacity);
        if (counter % modulus == 0 ) {
            moveToFront(key);
        } else {
            transpose(key);
        }
        if(entries.size() > capacity) {
            evict();
        }
        return this;
    }
    
    public boolean contains(T key) {
        return entries.containsKey(key);
    }
    
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private Entry current = head;
            @Override
            public boolean hasNext() {
                return (current != null);
            }

            @Override
            public T next() {
                T key = current.key;
                current = current.next;
                return key;
            }

            @Override
            public void remove() {
                //To change body of implemented methods use File | Settings | File Templates.
            }
        };
    }

    public int size() {
        return entries.size();
    }
}
